package com.zrrd.sort;

import java.util.Arrays;

public class ShellSort {
    public void shellSort(int[] array) {
        int step = array.length / 2;
        while (step >= 1) {
            for (int start = 0; start < step; start++) {
                insertionSort(array, step, start);
            }
            step = step / 2;
        }
    }

    public void insertionSort(int[] arr, int step, int start) {
        int temp;
        for (int i = start + step; i < arr.length; i += step) {
            for (int j = i; j - step >= start; j -= step) {
                if (arr[j] < arr[j - 1]) {
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 6, 7, 3, 2, 9, 1, 0, 5, 8};
        ShellSort ss = new ShellSort();
        ss.shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
